package ACM_Brush;

public class Solution215 {
    public static void main(String[] args) {
        int[] arr = new int[] { 3, 2, 1, 5, 6, 4 };
        System.out.println();
        // System.out.println(new solution_215().findKthLargest(arr, 2));
        new solution_215().quickSort(arr, 0, arr.length - 1);
        for (int a : arr) {
            System.out.println(a);
        }
    }
}

class solution_215 {
    // 1.快速选择算法
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);

    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivot = partition(nums, left, right);
        if (pivot == nums.length - k)
            return nums[pivot];
        else if (pivot > nums.length - k)
            return quickSelect(nums, left, pivot - 1, k);
        else
            return quickSelect(nums, pivot + 1, right, k);
    }

    // 2. 快速排序算法 
    public void quickSort(int[] nums, int left, int right) {
        if (left > right)
            return;

        int pivot = partition(nums, left, right);
        quickSort(nums, left, pivot - 1);
        quickSort(nums, pivot + 1, right);
    }

    // 3. 核心代码
    private int partition(int[] nums, int left, int right) {
        int pivotValue = nums[left]; // 保存最左侧的值，因为会第一个被覆盖
        while (left < right) {
            while (left < right && nums[right] >= pivotValue)
                right--;
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivotValue)
                left++;
            nums[right] = nums[left];
        }
        // 最终 left 的位置是 pivotValue 的最终位置，左侧都小于，右侧都大于
        nums[left] = pivotValue;
        return left;
    }

}
